package arvBinariaInteiros;

/**
* Laboratorio de Estrutura de Dados
* @author talitalm - 20921059
*/

public class ArvoreBinariaInteirosImpl implements ArvoreBinariaInteiros {
	private int dado = -1;
	private ArvoreBinariaInteirosImpl filhoEsquerda;
	private ArvoreBinariaInteirosImpl filhoDireita;
	
	/**
	 * analisa se a arvore eh vazia
	 */
	@Override
	public boolean isEmpty() {
		return (this.filhoEsquerda == null && this.filhoDireita == null);
	}

	/**
	 * analisa se o no em questao eh folha
	 */
	@Override
	public boolean isLeaf() {
		boolean resp = false;
		if(!isEmpty()){
			resp = this.filhoDireita.isEmpty() && this.filhoEsquerda.isEmpty(); 
		}
		return resp;
	}

	/**
	 * informa a altura da arvore
	 */
	@Override
	public int altura() {
		int resp = -1;
		if (!isEmpty()) {
			int alturaFilhoEsquerda = this.filhoEsquerda.altura();
			int alturaFilhoDireita = this.filhoDireita.altura();
			resp = 1 + maior(alturaFilhoEsquerda, alturaFilhoDireita);
		}
		return resp;
	}

	/**
	 * is not so bad
	 */
	private int maior(int valor1, int valor2) {
		int resultado = valor1;
		if (valor2 > valor1) {
			resultado = valor2;
		}
		return resultado;
	}
	
	/**
	 * pesquisa, na estrutura, a chave passada
	 */
	@Override
	public boolean pesquisar(int chave) {
		boolean resp = false;
		if (!isEmpty()) {
			if (this.dado == chave) {
				resp = true;
			} else {
				if (chave < this.dado) {
					resp = this.filhoEsquerda.pesquisar(chave);
				} else {
					resp = this.filhoDireita.pesquisar(chave);
				}
			}
		}
		return resp;
	}

	/**
	 * insere a chave - if for maior que a raiz no filhoDaDireita, else no filhoDaEsquerda
	 */
	@Override
	public void inserir(int chave) {
		if (isEmpty()) {
			this.dado = chave;
			this.filhoEsquerda = new ArvoreBinariaInteirosImpl();
			this.filhoDireita = new ArvoreBinariaInteirosImpl();
		} else {
			if (this.dado != chave) {
				if (chave < this.dado) {
					this.filhoEsquerda.inserir(chave);
				} else {
					this.filhoDireita.inserir(chave);
				}
			}
		}
	}

	/**
	 * remove, da estrutura, a chave passada
	 */
	@Override
	public void remover(int chave) {
		// TODO Auto-generated method stub
		/**
		 * No remover preocupe-se em analisar as seguintes situacoes:
		 * 1. se for arvore vazia - nao tem o que remover
		 * 2. se for folha - transforma o no em uma arvore vazia
		 * 3. se nao for folha - tenta capturar o menor descendente do filho a direita, transforma
		 *    ele na raiz e depois manda remover ele recursivamente. Se nao encontrar menor 
		 *    descendente a direita, pega o maior descendente do filho a esquerda, transforma ele 
		 *    na nova raiz e manda remover ele recursivamente.
		 */

		if (!isEmpty()) {
			if (this.dado < chave) {
				this.filhoDireita.remover(chave);
			} else if (this.dado > chave) {
				this.filhoEsquerda.remover(chave);
			} else {
				if (!(this.filhoDireita.isEmpty())) {
					int menorE = this.filhoDireita.minimo();
					this.dado = menorE;
					this.filhoDireita.remover(menorE);
				} else if (!(this.filhoEsquerda.isEmpty())){
					int maiorE = this.filhoEsquerda.maximo();
					this.dado = maiorE;
					this.filhoEsquerda.remover(maiorE);
				} else {
					this.dado = -1;
					this.filhoEsquerda = null;
					this.filhoDireita = null;
				}
			}
		}
	}
	
	
	/**
	 * extremo da direita
	 */
	@Override
	public int maximo() {
		int atual = -1;
		
		if (filhoDireita.isEmpty()) {
			atual = dado;
		} else {
			atual = filhoDireita.maximo();
		}
		return atual;
	}

	
	/**
	 * extremo da esquerda
	 */
	@Override
	public int minimo() {
		int atual = -1;
		
		if (filhoEsquerda.isEmpty()) {
			atual = dado;
		} else {
			atual = filhoEsquerda.minimo();
		}
		return atual;
	}

	// visitacao
	private void visita(ArvoreBinariaInteirosImpl objeto){
		System.out.println(objeto.getDado());
	}

	// captura o dado do no
	public int getDado() {
		return dado;
	}

	/**
	 * printa os elementos seguindo a pre-Ordem
	 */
	@Override
	public void preOrdem() {
		if (!isEmpty()) {
			visita(this); //
			this.filhoEsquerda.preOrdem();
			this.filhoDireita.preOrdem();
		}
	}

	/** 
	 * printa os elementos seguindo a ordem
	 */
	@Override
	public void ordem() {
		if (!isEmpty()) {
			this.filhoEsquerda.ordem();
			visita(this); //
			this.filhoDireita.ordem();
		}
	}
	
	
	/**
	 * printa os elementos seguindo a pos-Ordem
	 */
	@Override
	public void posOrdem() {
		if (!isEmpty()) {
			this.filhoEsquerda.posOrdem();
			this.filhoDireita.posOrdem();
			visita(this); //
		}
	}
	
	
	/**
	 * retorna o numero de elementos da estrutura
	 */
	@Override
	public int countElements(){
		int counterRight = 0;
		int counterLeft = 0;
		int counter = -1;

		if (isEmpty()) {
			counter++;
		} else {
			counterLeft = filhoEsquerda.countElements() + 1;
			counterRight = filhoDireita.countElements() + 1;
		}
		return counter + counterLeft + counterRight;
	}
}
